/*
	解法：用两个unordered_set<int>容器分别去重num1和num2，然后再作比较，最后用result保存
	为什么：“唯一 + 查找 + 无序”这三个关键词
	时间复杂度：O(m + n)，空间复杂度：O(m + n)
  
 */

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Solution
{
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
	{
		unordered_set<int> set1;
		unordered_set<int> set2;
		unordered_set<int> result;
		
		// 去重 nums1
		for (int i = 0; i < (int)nums1.size(); i++)
		{
			set1.insert(nums1[i]);
		}
		
		// 去重 nums2
		for (int i = 0; i < (int)nums2.size(); i++)
		{
			set2.insert(nums2[i]);
		}
		
		// 比较 set1 和 set2
		unordered_set<int>::iterator it;
		for (it = set2.begin(); it != set2.end(); ++it)
		{
			if (set1.count(*it))
			{
				result.insert(*it);
			}
		}
		
		return vector<int>(result.begin(), result.end());
	}
};

int main()
{
	Solution solution;
	
	vector<int> nums1 = {4, 9, 5};
	vector<int> nums2 = {9, 4, 9, 8, 4};
	
	vector<int> res = solution.intersection(nums1, nums2);
	
	cout << "Intersection: ";
	for (int i = 0; i < (int)res.size(); i++)
	{
		cout << res[i] << " ";
	}
	cout << endl;
	
	return 0;
}



